package problem912;

//912.排序数组
//https://leetcode.cn/problems/sort-an-array/

//归并

class Solution3 {
    public int[] sortArray(int[] nums) {
        mergeSort(nums, 0, nums.length-1);
        return nums;
    }
    public static void mergeSort(int[] nums, int left, int right) {
        if(left >= right) return;

        int mid = left + (right - left)/2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid+1, right);

        //[left, mid] [mid+1, right]
        int k1 = left, k2 = mid+1;
        int[] tmp = new int[right-left+1];
        int index = 0;
        while(k1 <= mid && k2 <= right) {
            if(nums[k1] < nums[k2]) {
                tmp[index++] = nums[k1++];
            }else {
                tmp[index++] = nums[k2++];
            }
        }
        while(k1 <= mid) {
            tmp[index++] = nums[k1++];
        }
        while(k2 <= right) {
            tmp[index++] = nums[k2++];
        }
        //拷贝回原数组
        for(int i = left; i<=right; i++) {
            nums[i] = tmp[i-left];
        }
    }
}